package ljl.alg.jianzhioffer.round2;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 1. 排序
 * 2. 堆
 * 3. 快速选择排序
 * */
public class _40_min_k {
    
    public int[] getLeastNumbers1(int[] arr, int k) {
        Arrays.sort(arr);
        return Arrays.copyOf(arr, k);
    }
    
    public int[] getLeastNumbers2(int[] arr, int k) {
        int[] res = new int[k];
        if (k == 0)
            return res;
        PriorityQueue<Integer> q = new PriorityQueue<>(k, (a, b) -> b - a);
        for (int i : arr) {
            q.offer(i);
            if (q.size() > k)
                q.poll();
        }
        int i = 0;
        for (Integer each : q) {
            res[i++] = each;
        }
        return res;
    }
    
    // 标准解法，快速选择排序
    public int[] getLeastNumbers(int[] arr, int k) {
        partialSort(arr, 0, arr.length - 1, k);
        return Arrays.copyOf(arr,k);
    }
    
    /**
     * 闹了半天，== 是可以的
     * 只是他的输入比较特殊，它输入了 k == 0
     * 王八羔子！
     * */
    void partialSort(int[] arr, int from, int to, int k) {
        // 你得知道这里 == 是不行的！
        // 为什么这里不能是 ==？？？？？一直没搞明白
        if (from >= to) return;
        int pivot = arr[from];
        int l = from, r = to;
        while (l < r) {
            while (l < r && arr[r] >= pivot) r--;
            arr[l] = arr[r];
            while (l < r && arr[l] <= pivot) l++;
            arr[r] = arr[l];
        }
        arr[l] = pivot;
        if (l == k - 1) return;
        if (l > k - 1) partialSort(arr, from, l - 1, k);
        else partialSort(arr, l + 1, to, k);
    }
    
    /**
     * 这么写，from == to 是没问题的
     * 注意最下面判断是 == k
     * */
    void partialSort2(int[] arr, int from, int to, int k) {
        if (from == to) return;
        int pivot = arr[from];
        int l = from, r = to;
        while (l < r) {
            while (l < r && arr[r] >= pivot) r--;
            arr[l] = arr[r];
            while (l < r && arr[l] <= pivot) l++;
            arr[r] = arr[l];
        }
        arr[l] = pivot;
        if (l == k) return;
        if (l > k) partialSort(arr, from, l - 1, k);
        else partialSort(arr, l + 1, to, k);
    }
    
}
